/*
给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
*/
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 字符串s在left和right位置处向旁边扩散可得到的最大回文字符串长度
    int expand(string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        // 想象一开始left和right位置就不相等应该返回0
        return right - left - 1;
    }

    string longestPalindrome(string s) {
        int left = 0;
        int right = 0;

        for (int i = 0; i < s.size(); i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i + 1);

            int len = max(len1, len2);

            if (right - left + 1 < len) {
                left = i - (len - 1) / 2;
                right = len + left - 1;
            }
        }

        return s.substr(left, right - left + 1);
    }
};

int main() {
    cout << Solution().longestPalindrome("babad") << endl;
    return 0;
}